#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 图的邻接表表示
class Graph {
private:
    int V; // 顶点数
    vector<int> *adj; // 邻接表

public:
    Graph(int V); // 构造函数
    void addEdge(int v, int w); // 添加边
    void BFS(int s); // 广度优先搜索
};

// 构造函数
Graph::Graph(int V) {
    this->V = V;
    adj = new vector<int>[V];
}

// 添加边
void Graph::addEdge(int v, int w) {
    if (v >= 1 && v <= V && w >= 1 && w <= V) {
        adj[v-1].push_back(w-1); // 添加w到v的邻接表，注意索引偏移
        adj[w-1].push_back(v-1); // 由于是无向图，也需要添加v到w的邻接表，注意索引偏移
    } else {
        cerr << "错误: 边 (" << v << ", " << w << ") 的顶点超出范围 [1, " << V << "]" << endl;
    }
}

// 广度优先搜索
void Graph::BFS(int s) {
    if (s < 1 || s > V) {
        cerr << "错误: 起始顶点 " << s << " 超出范围 [1, " << V << "]" << endl;
        return;
    }

    bool *visited = new bool[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    queue<int> q;

    visited[s-1] = true; // 注意索引偏移
    q.push(s-1); // 注意索引偏移

    while (!q.empty()) {
        int u = q.front();
        cout << (u + 1) << " "; // 输出时还原顶点编号
        q.pop();

        for (auto i = adj[u].begin(); i != adj[u].end(); ++i) {
            if (!visited[*i]) {
                visited[*i] = true;
                q.push(*i);
            }
        }
    }

    delete[] visited;
}

int main() {
    int V, E, startVertex;

    // 输入顶点数
    cout << "请输入顶点数: ";
    cin >> V;
    if (V <= 0) {
        cerr << "错误: 顶点数必须大于 0" << endl;
        return 1;
    }

    // 创建图
    Graph g(V);

    // 输入边数
    cout << "请输入边数: ";
    cin >> E;
    if (E < 0) {
        cerr << "错误: 边数不能为负数" << endl;
        return 1;
    }

    // 输入边的信息
    cout << "请输入边的信息 (每行两个顶点):" << endl;
    for (int i = 0; i < E; i++) {
        int v, w;
        cin >> v >> w;
        g.addEdge(v, w);
    }

    // 输入起始顶点
    cout << "请输入起始顶点: ";
    cin >> startVertex;

    cout << "广度优先搜索遍历 (从顶点 " << startVertex << " 开始): ";
    g.BFS(startVertex);

    return 0;
}